The present invention relates to processing of digital and analog signals, and more particularly to the computational techniques used in Finite Impulse Response ("FIR") digital filters.
The uses and advantages of FIR filters are well known. In operation and with reference to FIGS. 1 and 2, an FIR digital filter receives an input signal S.sub.IN that may be in analog or digital format, filters the input signal, and provides a state-of-the-filter output signal S.sub.OUT that is responsive to the filter characteristics. Typically, FIR digital filters sum the products of plural discrete signal values (S.sub.0, S.sub.-1, S.sub.-2, . . . , S.sub.-M), where M is the number of filter taps, times weighting coefficients (A.sub.0, A.sub.1, A.sub.2, . . . , A.sub.M) using the following formula: EQU S.sub.OUT =S.sub.0 A.sub.0 +S.sub.-1 A.sub.1 +S.sub.-2 A.sub.2 +. . . +S.sub.-M A.sub.M ( 1)
to produce the state-of-the-filter output signal S.sub.OUT. Often the signal values (S.sub.0, S.sub.-1, . . . S.sub.M) are related to each other in time, i.e., S.sub.0 is the state of the input signal at T=0, S.sub.-1 the signal at a previous time (T.sub.-1), S.sub.-2 is the signal at a second previous time (T.sub.-2), etc.
As can be appreciated from Equation (1), in a FIR filter with M taps, at least M multiplication operations (and additions), typically conducted sequentially, are required each time the output signal is updated. Because multiplication is a relatively time-consuming process in digital circuitry, the process of multiple, sequential multiplications often limits the effectiveness of FIR filters, especially in wideband data applications.
With further reference to FIG. 2, a typical FIR digital filter may be seen. In the filter, an input signal S.sub.IN is periodically sampled and converted from analog to digital in a converter 10 to produce a discrete signal S.sub.0. The signal S.sub.0 is fed to delay elements 12 where it is to be used with subsequent discrete signals S.sub.0, and to a multiplier 14 where it is multiplied by a coefficient A.sub.0. The various signals S.sub.0. . . S.sub.-M are multiplied by their respective coefficients A.sub.0. . . A.sub.M and these products are summed in adder 16. The summed digital signal is fed to a digital to analog converter 18 to produce an output signal S.sub.0UT. The coefficients A.sub.0 through A.sub.M are chosen using techniques known in the art to produce an appropriate filter response. The filter of FIG. 2 parallels all of the multiplications, so that the time to perform the calculation of S.sub.0UT at each output sample time is reduced substantially but at a substantial increase in complexity (and usually, cost) of the filter which now requires M multipliers and an adder which can access each multiplier. Note that the filter of FIG. 2 still requires at least M additions performed sequentially after a multiplication. Obviously, with a further increase in complexity, the M sequential additions could be carried out using more parallel processing to add, in parallel, predetermined sets of the A.sub.0 S.sub.0. . . A.sub.M S.sub.-M products to produce plural subtotals which can be added sequentially to produce the output of the adder 16.
To reduce the computational time in digital filters, it is known to replace the coefficient multipliers with shift registers. In such systems, as disclosed in U.S. Pat. No. 4,691,233 to Conboy, the input signal is sampled by an analog-to-digital converter which produces a digital signal representing the power of two most closely corresponding to the value of the input signal. The power-of-two digital signal is subsequently used to shift the various co-efficients A.sub.0. . . A.sub.M (rather than multiply) to produce the plural products which may be added by the adder. Because digital shifting operations are generally much faster than digital multiplying, the shifting filters are generally faster, albeit with some loss of accuracy and/or responsiveness of the filter. The shifting filter also generally requires that M addition steps be performed after the shifting operations, limiting the effectiveness of such filters in wide bandwidth systems.
As is known, in some applications FIR filter input signals S.sub.-M may assume two values: 0 or 1. Thus, each product S.sub.-M A.sub.M may take on one of two values: 0 or A.sub.M. Where the coefficients A.sub.0. . . A.sub.M are fixed in a binary input system, the output signal, S.sub.OUT, may take any one of 2.sup.M values. In some prior art systems, it is known to precompute the 2.sup.M S.sub.OUT values and to store the values of 2.sup.M S.sub.OUT in a suitable memory where they may be addressed using the sequence of input data. (See, for example, U.S. Pat. No. 4,953,184 to Simons). For example, in a filter having eight taps at which the signal value may be 0 or 1, all of the possible states of the filter may be stored in 256 (2.sup.8) storage locations. However, where the number of filter taps M is large, for example in a 95 tap filter, the number of memory locations required to store all of the 2.sup.M values becomes very large (e.g., 3.96.times.10.sup.28 locations for a 95 tap system) so as to become very expensive, even if possible to implement in hardware.
It is known in digital filters that the output rate of the filter may differ from the input rate. For example, the output rate may exceed the input rate and, accordingly, states of the filter may be generated at a rate faster than the input data are sampled. In such circumstances, the sampled input data may be repeated, i.e., not updated, while the output state of the filter is computed several times. If, for example, the output state of the filter is being computed at a rate which is four times faster than the input data are being sampled, the filter would have four newly-computed output states for each sample of the input. Generally, in such systems, the digital filter uses as its digital input the last sample of the input signal. Thus, in the above example, each digital input (from the input sampling) would be used four consecutive times before a new sample is taken.
The present invention uses the relationship between the rate of the output signal and the rate of the input samples to significantly reduce the amount of memory required for storage of the precomputed coefficients. The difference between the sample rate and the output rate essentially constrains the number of possible states of the filter. For example, if a filter has eight taps and an input which is sampled as frequently as the output state of the filter is computed, a table of 2.sup.8 words (256) would be needed to store all of the possible states of the filter. If, however, the output states of the filter are determined at a rate twice as fast as the input data is being sampled, each time the input is sampled two identical inputs are effectively obtained. The number of possible states of the filter is reduced because each signal S.sub.0. . . S.sub.N is not free to vary but is constrained to be identical to one of its adjacent signals. The number of possible states of the filter is reduced to (2).times.(2.sup.4)=32 words. In general, this relationship between the input and output rates and memory requirements may be expressed in an M tap system as Memory=2 times X.sup.M where X is the number of permissible signal values (e.g., , X=2 for binary signals). In accordance with one aspect of the present invention, the S.sub.OUT values may be addressed by using the input data pattern and a cycling counter or position indicator which reflects the number of times the current input data has been repeated.
Accordingly, it is an object of the present invention to provide a novel method and device for filtering a digital or analog signal in a FIR filter that increases filter throughput so that the filter can operate with a large number of taps.
It is a further object of the present invention to provide a novel FIR digital filter and method in which the states of the filter may be determined from a lookup table.
It is yet a further object of the present invention to provide a novel FIR digital filter in which the states of the filter are stored in a memory and addressed using input data patterns and positional information.
It is still a further object of the present invention to provide a novel device and method for filtering an input signal with an FIR filter that has a memory for storing states of the filter where the memory is addressed with an N bit address signal comprising P bits of a pattern of data from an input signal and N-P bits of pattern position data.
These and many other objects and advantages of the present invention will be readily apparent to one skilled in the art to which the invention pertains from a perusal of the claims and the following detailed description of preferred embodiments when read in conjunction with the appended drawings.